#include "main/utils.h"
#include "lib/list.h"
using namespace std;

ListNode* theFirstCommonNode_stack(ListNode* phead1, ListNode* phead2) {
  if (!phead1 || !phead2)
    return nullptr;

  stack<ListNode*> stack1;
  stack<ListNode*> stack2;
  auto node1 = phead1;
  auto node2 = phead2;
  while (node1) {
    stack1.push(node1);
    node1 = node1->next;
  }
  while (node2) {
    stack2.push(node2);
    node2 = node2->next;
  }
  node1 = stack1.top();
  node2 = stack2.top();
  ListNode* common_node = nullptr;
  while (node1 == node2) {
    common_node = node1;
    stack1.pop();
    stack2.pop();
    node1 = stack1.top();
    node2 = stack2.top();
  }
  return common_node;
}

ListNode* theFirstCommonNode_iter(ListNode* phead1, ListNode* phead2) {
  if (!phead1 || !phead2) {
    return nullptr;
  }
  auto node1 = phead1;
  auto node2 = phead2;
  int length1 = 0, length2 = 0;
  while (node1) {
    ++length1;
    node1 = node1->next;
  }
  while (node2) {
    ++length2;
    node2 = node2->next;
  }
  int diff_length = 0;
  ListNode* faster_node = nullptr;
  ListNode* slower_node = nullptr;
  if (length2 > length1) {
    diff_length = length2 - length1;
    faster_node = phead2;
    slower_node = phead1;
  } else {
    diff_length = length1 - length2;
    faster_node = phead1;
    slower_node = phead2;
  }
  for (int i = 0; i < diff_length; ++i) {
    faster_node = faster_node->next;
  }
  while (faster_node != slower_node) {
    faster_node = faster_node->next;
    slower_node = slower_node->next;
  }

  return faster_node;
}

int main() {
  auto node1 = CreateNode(1);
  auto node2 = CreateNode(2);
  auto node3 = CreateNode(3);
  auto node4 = CreateNode(4);
  auto node5 = CreateNode(5);
  auto node6 = CreateNode(6);
  auto node7 = CreateNode(7);

  ConnectNode(node1, node2);
  ConnectNode(node2, node3);
  ConnectNode(node3, node6);
  ConnectNode(node6, node7);
  ConnectNode(node4, node5);
  ConnectNode(node5, node6);

  auto ret_stack = theFirstCommonNode_stack(node1, node4);
  auto ret_iter = theFirstCommonNode_iter(node1, node4);
  cout << "Find the first common list node by stack: " << ret_stack->value << endl;
  cout << "Find the first common list node iteratively: " << ret_iter->value << endl;

  return 0;
}
